#include "ce_core.h"
#include "ce_tester.h"

using namespace CETester;

int32_t CheckRbtreeNode(ce_rbtree_node_t *rn, unsigned c) {
    int32_t leftbb, rightbb;

    if (rn == NULL) {
        return 1;
    }

    if (c == RED && rn->c == RED) { // 父节点和本节点均为红色
        TestErrorf("Check Rbtree node(%llu) error: parent node and current node are red", rn->k);
        return -1;
    }

    leftbb = CheckRbtreeNode(rn->l, rn->c);
    rightbb = CheckRbtreeNode(rn->r, rn->c);

    if (leftbb < 0) {
        return leftbb;
    }

    if (rightbb < 0) {
        return rightbb;
    }

    if (leftbb != rightbb) { // 节点两颗子树的黑色节点数不同
        TestErrorf("Check Rbtree node(%llu) error: left branch blk depth %d,"
            " right branch blk depth %d, are not equal", rn->k, leftbb, rightbb);
        return -1;
    }

    return leftbb++;
}

// 红黑树性质
// 1. 根节点为黑色
// 2. 每个叶子（nil）节点为黑色
// 3. 如果一个节点为红色，它的两个子节点都为黑色
// 4. 对每个节点，该节点到其所有后代叶节点的简单路径上，均包含相同数量的黑色节点
bool CheckRbtree(ce_rbtree_t *rbt) {
    if (rbt->root == NULL) { // 空树
        return true;
    }

    if (rbt->root->c != BLK) { // 树根不为黑色
        TestErrorf("Check Rbtree error: root is not black");
        return false;
    }

    if (CheckRbtreeNode(rbt->root, rbt->root->c) >= 0) {
        return true;
    }

    return false;
}

CE_TESTCASE(RbtreeTestInsert) {
}

CE_TESTCASE(RbtreeTestDelete) {
}

int main() {
    RunAllTester();
}
